package offer2

import "container/list"

/*
原题链接:
https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

B站 帅地玩编程
剑指offer 31.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。

例如，序列 {1,2,3,4,5} 是某栈的压栈序列，
序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，

但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

思路:
		i
pushed: 1 2 3 4 5
poped:  4 5 3 2 1
		k

		-------------------------------------------------------
														1|  stack
		---------------------------------------------------

声明i,k指针分别指向0下标
用一个辅助栈, 按照pushed顺序进行入栈操作
	入栈过程中,
		当入栈动作到元素4时候, 和k指针相等, 说明需要出栈, 将4从栈顶弹出
		k++, 然后判断k元素是否还跟当前栈顶元素相等
		不相等, 继续进行i的入栈动作
		入栈5, 和k元素相等, 弹出当前栈顶元素

		以此类推,
		入栈3, 和栈顶元素相等, 弹出, k++
		入栈2, 和栈顶元素相等, 弹出, k++
		入栈1, 和栈顶元素相等, 弹出, k++

		最终k能到达数组末尾位置, 所以是该栈的弹出顺序
*/

func validateStackSequences(pushed []int, popped []int) bool {
	if pushed == nil || len(pushed) == 0 { //1.如果pushed为nil或者长度为0, 直接返回true
		return true
	}

	k := 0              //2.当前遍历到的位置
	stack := list.New() //3.创建数组
	n := len(pushed)

	for i := 0; i < n; i++ { //4.遍历数组
		stack.PushBack(pushed[i]) //4.1放入栈尾部

		for stack.Len() > 0 && stack.Back().Value.(int) == popped[k] { //4.2 stack.Back(): 用于获取链表的最后一个元素
			stack.Remove(stack.Back()) //删除尾部元素
			k++
		}
	}

	//5.返回栈中是否为空
	return stack.Len() == 0
}
